home *** CD-ROM | disk | FTP | other *** search
/ Games of Daze / Infomagic - Games of Daze (Summer 1995) (Disc 1 of 2).iso / x2ftp / msdos / theory / collide / collide.pas < prev   
Encoding:
Pascal/Delphi Source File  |  1995-04-18  |  7.5 KB  |  183 lines
  1. {*****************************************************************************}
  2. {*                                                                           *}
  3. {*                               COLLIDE                                     *}
  4. {*                                v 1.0                                      *}
  5. {*                                                                           *}
  6. {*                          (C) 1995 M.Mackey.                               *}
  7. {*                                                                           *}
  8. {*  I present here some sample code for very fast pixel-precision collision  *}
  9. {*  detection. This code should be easy to add to any existing sprite engine *}
  10. {*  that uses bounding-box collision detection. The one limitation is that   *}
  11. {*  sprites are assumed to be of less than 32 pixels in width (although it   *}
  12. {*  would be reasonably easy to extend the code to allow 64-pixel wide       *}
  13. {*  sprites). See the file COLLIDE.DOC for more information.                 *}
  14. {*                                                                           *}
  15. {*                                                                           *}
  16. {*****************************************************************************}
  17.  
  18. unit collide;
  19.  
  20. interface
  21. const MaxSpriteHeight=24; {No hard limit: set to whatever your maximum
  22.                            height actually is}
  23. type masktype=array[0..MaxSpriteHeight-1] of longint;
  24.                           {holds the mask}
  25.      maskptr=^masktype;
  26.      longarray=array[1..60000] of byte;
  27.                           {A kludge used for accessing random bytes in
  28.                            dynamically allocated variables}
  29.  
  30. function CollideBitmaps(mask1:masktype;height1,x1,y1:integer;
  31.                          mask2:masktype;height2,x2,y2:integer):boolean;
  32. procedure MakeMask(var p:longarray;var mask:maskptr);
  33.  
  34. implementation
  35.  
  36. {*****************************************************************************
  37.  Function CollideBitmaps(mask1:masktype;height1,x1,y1:integer;
  38.                          mask2:masktype;height2,x2,y2:integer):boolean;
  39.  
  40.  Checks bitmap collisions.
  41.  
  42.  Mask1:   The mask for sprite 1
  43.  Height1: The height of sprite 1
  44.  x1, y1:  The screen coordinates of the top left corner of sprite 1
  45.  Mask1:   The mask for sprite 2
  46.  Height1: The height of sprite 2
  47.  x1, y1:  The screen coordinates of the top left corner of sprite 2
  48.  
  49.  Sprite 1 must be to the left of sprite 2,and the bounding boxes _must_
  50.  have collided
  51.  ie x1<=x2, 0<=(x2-x1)<=31 are assumed, and the y extents of the two
  52.  sprites must overlap.
  53.  
  54.  Use an initial bounding box check to set this up
  55.  eg (from the XQuest code, assuming short-cut boolean evaluation $B-)
  56.  
  57.   for i:=NumEnemies downto 1 do
  58.   with enemy[i] do
  59.   begin
  60.     if (xbr>=ship.x) and (ybr>=ship.y) and
  61.        (x<=ship.xbr) and (y<=ship.ybr) then
  62.        if ((ship.x<=x) and
  63.           CollideBitmaps(ship.mask^,ship.height,ship.x,ship.y,mask^,height,x,y))
  64.          or ((x<ship.x) and
  65.           CollideBitmaps(mask^,height,x,y,ship.mask^,ship.height,ship.x,ship.y))
  66.        then they have collided....
  67.  
  68.     where x and y are the coords of the top left hand corner and xbr and ybr
  69.     the coords of the bottom right hand corner of the sprite.
  70.  
  71.     Such a bounding box check is very fast, and the more computationally
  72.     expensive mask check is thus called only rarely  (and hence does not
  73.     need to be optimised _too_ much...)
  74.  
  75. *****************************************************************************}
  76.  
  77. function CollideBitmaps(mask1:masktype;height1,x1,y1:integer;
  78.                         mask2:masktype;height2,x2,y2:integer):boolean;assembler;
  79. asm
  80.         push    ds
  81.         mov     cx,x2
  82.         sub     cx,x1         {0<=cx<=31, difference in x-coords}
  83.  
  84.         mov     ax,word ptr [height1]   {loop counter}
  85.  
  86.         lds     si,mask1
  87.         les     di,mask2      {ds:si and es:di point to the two masks}
  88.         mov     ax,[y2]
  89.         sub     ax,[y1]       {ax is set to the difference in the y coords}
  90.         jl      @Mask2Upper   {which sprite has a lower y coord?}
  91.  
  92. {Mask 1 uppermost:}
  93.         mov     dx,[height1]
  94.         sub     dx,ax         {# of dwords of overlap of first mask with second}
  95.                               {  ie number of rows to be compared}
  96.         cmp     dx,[height2]  {will this run below the end of the second sprite?}
  97.         jle     @HeightOK1
  98.         mov     dx,[height2]  {Yes, set number of rows to be compared to the height of sprite 2}
  99. @HeightOK1:
  100.         shl     ax,2          {# of dwords to skip in first mask}
  101.         add     si,ax         {si now points to top of overlap of 1st mask
  102.                                with second}
  103.  
  104. @OverlayLoop:
  105.         db      $66
  106.         mov     ax,word ptr ds:[si]   {mov eax, dword ptr ds:[si]}
  107.                               {Get mask entry for 1st sprite}
  108.         db      $66
  109.         shl     ax,cl         {shl eax, cl}
  110.                               {Shift left by amount of overlap}
  111.         db      66h
  112.         and     ax,word ptr es:[di]   {and eax, dword ptr es:[di]}
  113.                               {Compare with 2nd sprite mask entry}
  114.         jnz     @collision    {If non-zero then the sprites collided}
  115.  
  116.  
  117.         add     si,4
  118.         add     di,4          {otherwise, check the next mask entries}
  119.         dec     dx            {Any more rows to be checked?}
  120.         jnz     @overlayloop
  121.         jmp     @nocollision  {No, report no collision}
  122.  
  123. @Mask2Upper:                  {Mask 2 is uppermost}
  124.         neg     ax
  125.         mov     dx,[height2]
  126.         sub     dx,ax         {# of dwords of overlap of second mask with first}
  127.                               {  ie number of rows to be compared}
  128.         cmp     dx,[height1]  {will this run below the end of the first sprite?}
  129.         jle     @HeightOK2
  130.         mov     dx,[height1]  {Yes, set number of rows to be compared to the height of sprite 1}
  131. @HeightOK2:
  132.         shl     ax,2          {# of dwords to skip in second mask}
  133.         add     di,ax         {di now points to top of overlap of 2nd mask
  134.                                with first}
  135.         jmp     @OverlayLoop
  136.  
  137. @Collision:
  138.         mov    ax,1           {Yes, collision detected. Return TRUE}
  139.         jmp    @finished
  140.  
  141. @NoCollision:
  142.         mov    ax,0           {No collision detected, return FALSE}
  143. @finished:
  144.         pop    ds
  145. end;
  146.  
  147. {*****************************************************************************
  148. procedure MakeMask(var p:longarray;var mask:maskptr);
  149.  
  150.   Makes a mask for a sprite from a XBM (Xlib linear bitmap).
  151.   Format: height (1 byte)
  152.           width (1 byte)
  153.           bitmap data (width*height bytes)
  154.  
  155.   p holds a sprite with the above structure
  156.   mask should not be pre-allocated
  157. *****************************************************************************}
  158.  
  159. procedure makemask(var p:longarray;var mask:maskptr);
  160. var i,j,Height,Width:integer;
  161. const bits:array[0..31] of longint=
  162.   ($8000,$4000,$2000,$1000,$800,$400,$200,$100,$80,$40,$20,$10,$8,$4,$2,$1,
  163.    $80000000,$40000000,$20000000,$10000000,$8000000,$4000000,$2000000,
  164.    $1000000,$800000,$400000,$200000,$100000,$80000,$40000,$20000,$10000);
  165.  {mask for the 32 bits in a dword. Note the word order in a dword on the
  166.   PC!}
  167.  
  168. begin
  169.   Width:=p[1];
  170.   Height:=p[2];
  171.   getmem(mask,Height*4);   {get memory for mask}
  172.   for i:=0 to (Height-1) do
  173.   begin
  174.     j:=1;
  175.     mask^[i]:=0;
  176.     for j:=1 to Width do
  177.      if (p[i*Width+j+2]<>0) then
  178.         mask^[i]:=mask^[i] or (bits[j]);
  179.   end;
  180. end;
  181.  
  182. end.
  183.